The present invention relates generally to integrated circuit memories, and more specifically to set associative cache memories.
During the manufacture of integrated circuit memory devices, die are often discarded when certain bits of the die are defective but not easily identified and repaired. Even though a majority of the die may be fully functional, it is often necessary to discard the entire die if the faulty bits of the die are not repairable. This problem is exacerbated when a memory device is embedded in another, more expensive device such as a microprocessor or an application specific integrated circuit (ASIC). For example, it is undesirable to discard a costly microprocessor because the memory embedded within it has faulty bits. Memories which may have faulty bits include cache memories, memory cards, and memories embedded in ASICs.
Cache memories are important elements of the typical cache system and are increasingly used as primary caches embedded in high performance microprocessors or as secondary caches external to the microprocessor. As microprocessors have achieved faster operating speed, the rate at which requested data must be supplied to them has correspondingly increased. Cache memories typically have faster access times than main memory and thus are often used to quickly supply data requested by the microprocessor. The tag associated with a "line" of data, a block of data which can be one or several consecutive bytes or words of data, in the cache memory is stored in a tag RAM which holds the address locations of data stored in the data cache. In addition to address information, one or more status bits, often including a valid bit which indicates whether data stored at a particular address location is valid or invalid, is stored in the tag RAM. When the microprocessor requests information, a read signal is sent to both the main memory and the tag RAM. The tag RAM compares the requested memory address with the memory address of all data stored in the cache memory. If the requested memory address is in the tag RAM, a "hit" condition exists, and data from that location will be gated from the cache memory to the microprocessor.
In a "hit" condition, the tag RAM generates a valid compare Match output signal and the cache memory gates the required data onto the data bus before the main memory can respond. In this way, the cache memory quickly supplies data to the microprocessor and microprocessor wait states are avoided. However, if the tag RAM's comparison operation indicates that the desired data is not stored inside the cache memory, a "miss" condition exists, and the data must come from main memory which typically holds more data than the cache memory and is therefore much slower. As a result, the microprocessor may have to wait for several cycles, during which time it is idle, before receiving requested data from main memory. These unproductive cycles are referred to as "wait states" since the microprocessor must wait until the requested data is provided from main memory.
In place of the direct-mapped cache memory described above, set-associative cache memories are often used because of the performance enhancement they can provide. In a set-associative cache memory, there are two or more "sets" from which data may be supplied to the microprocessor. Thus, if one set does not contain the requested data, another set may very well be able to provide valid data. In a two-way set-associative cache system, for example, the cache is split into two smaller, somewhat independent caches. This allows for two tags to be stored for a given index address and the two associated lines of data in each cache memory; the index of the tag is the least significant bits (LSBs) of the address field, used to address a given tag location, and the tag bits are the most significant bits (MSBs). Set-associative cache systems typically possess higher hit rates than a comparable direct mapped cache, although there is added complexity embodied in replacement algorithms which determine what cache location of which tag RAM to overwrite upon a miss condition.
FIG. 1 shows a block diagram of a set-associative cache system 10 which is comprised of five main elements: microprocessor 12, main memory 13, tag RAM A 14, tag RAM B 16, cache memory set A 18, cache memory set B 19, and control logic 20. Because the cache memory is separate from the microprocessor, cache system 10 is a secondary cache system which is shown for clarity. In a primary cache system, cache memory set A 18 and set B 19 would be embedded in the microprocessor, and thus is sometimes called an embedded cache memory. Microprocessor 12 could obtain all needed data from the slow main memory 13. However, since main memory 13 is typically much slower than microprocessor 12, microprocessor 12 will incur "wait states" until the data arrives from main memory 13. During wait states, microprocessor 12 is idle. Wait states have a negative impact on the efficiency of the microprocessor.
For these reasons, a cache system is used to provide the microprocessor with data in a more timely fashion, in the hopes of reducing or even eliminating microprocessor wait states. The secondary cache system, composed of tag RAM A 14, tag RAM B 16, cache memory set A 18, cache memory set B 19, and control logic 20, resides between microprocessor 12 and main memory 13. Set A 18 and set B 19 together comprise a two-way set associative cache memory and each store a copy of frequently accessed main memory data. Storing data commonly accessed by the microprocessor 12 increases the likelihood that cache memory set A 18 or set B 19 will have the requested data in the event of a microprocessor memory cycle.
Transparent to main memory 13, either cache memory set A 18 or cache memory set B 19 will supply data to microprocessor 12 upon a microprocessor read cycle if they have the requested data. Tag RAM A 14 determines if cache memory set A 18 has the data requested by the microprocessor 12 while tag RAM B 16 determines if cache memory set B 19 has the requested data; Tag RAM A 14 stores the memory addresses and status bit information of data stored in cache memory set A 18 and tag RAM B 16 stores the memory addresses and status bit information of data stored in cache memory set B 19. Valid bit 17 is a status bit which indicates whether the data stored at a particular address location is valid or invalid. The valid bits of address locations stored in tag RAM A 14 and tag RAM B 16 are typically cleared by resetting the value of the valid bit for all address locations in the tag RAM through software or hardware means at the start of a new process or program. Valid bit 17 is tied to a logic high voltage level, V.sub.CC, as shown in FIG. 1, such that subsequent write cycles from microprocessor 12 write a "one" to newly written tag RAM address locations. Until microprocessor 12 writes data to a cache memory location, the valid bit 17 for that address location will be invalid or equal to a logic low level.
Upon a microprocessor read, the tag RAM A 14 and tag RAM B 16 compare the address of the data being sought with the addresses of data stored in the cache memory set A 18 and cache memory set B 19, respectively. If a "hit" or match condition exists in either set A 18 or set B 19 and the valid bit 17 as well as other status bits for that address index location are valid, the appropriate tag RAM A 14 or tag RAM B 16 generates a logic high Match output signal 15 which indicates that its cache memory set A 18 or set B 19 has the desired data. Control logic 20 determines which set will provide the data as a function of the match and status bits, and data from the appropriate set of the cache memory is then gated onto the data bus where it is received by microprocessor 12. If, however, tag RAM A 14 or tag RAM B16 determines the desired data address does not match any addresses stored in the cache memory set A 18 or cache memory set B 19, respectively, a "miss" condition for that set exists. Or, if the desired data address matches an address stored in cache memory set A 18 or cache memory set B 19 but valid bit 17 for that address is invalid, a "miss" condition also exists. In response to a "miss" condition, the tag RAM generates a logic low Match output signal.
Once it has been determined that cache memory set A 18 or cache memory set B 19 contains the data of the memory address being requested and that the data is valid, the associated tag RAM generates Match output signal 15. Match output signal 15 functions as a high-speed chip select which allows or does not allow data from the cache memory to be gated onto the data bus to the microprocessor. If the tag RAM comparison function indicates a "hit" condition then the cache memory outputs are simply enabled. If a "miss" condition is indicated, the outputs of the appropriate cache memory set are not enabled and main memory 13 will ultimately supply the data to the microprocessor 12. When a "miss" occurs, replacement algorithms, such as the least recently used (LRU), the first in first out (FIFO), the last in first out (LIFO), the random replacement algorithm, and the pseudo LRU replacement algorithm are used to determine whether a replacement line of data from main memory will be used to update set A 18 or set B 19. This parallel activity during cache memory read cycles saves time and can possibly allow the data to be read by microprocessor 12 in a single cycle, with no wait states.
A set associative cache memory where one or more sets have randomly occurring bit(s) failures is often discarded. Unfortunately, set associative cache memories may suffer from bit failures due to randomly occurring process problems such as single bit failures, particle contamination, locked rows, locked columns, and metal or polysilicon shorts. These failures may not be easily repaired, especially if no row or column redundancy testing is employed. Even when redundancy testing at laser repair is used, this technique may not be sufficient to ferret out all bit failures. Therefore, when a set associative cache memory having bit(s) failures is resident in microprocessors, ASICs, or other devices, both the faulty cache memory and the expensive fully functional device in which it is embedded are often discarded. Thus, there is a current unmet need in the art to compensate for random bit(s) failures such that set associative cache memories having faulty data bits are rendered usable. It would be desirable to bypass defective data locations in the set associative cache memory such that the cache memory and any device in which it is embedded need not be scrapped.